{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### heapq的使用"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://docs.python.org/zh-cn/3.7/library/heapq.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from heapq import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "nums = [3,2,8,3,5,6,1,1,0,9,3,7,5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 1, 3, 5, 6, 3, 3, 9, 5, 8, 7]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 创建一个堆，方法1\n",
    "h = []\n",
    "for val in nums:\n",
    "    heappush(h, val)\n",
    "h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 1, 2, 3, 5, 8, 3, 3, 9, 5, 7, 6]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 创建一个堆，方法2\n",
    "h = nums\n",
    "heapify(h)\n",
    "h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 弹出最小元素\n",
    "heappop(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 5, 2, 3, 6, 8, 3, 3, 9, 5, 7]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 堆排序\n",
    "def heapsort(nums):\n",
    "    h = []\n",
    "    for val in nums:\n",
    "        heappush(h, val)\n",
    "    return [heappop(h) for i in range(len(h))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 堆的实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 堆，堆是一种特殊的完全二叉树\n",
    "# 最小堆，所有父节点比子节点小\n",
    "# 使用数组储存\n",
    "class Heap(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.vals = []\n",
    "        \n",
    "    def __len__(self):\n",
    "        return len(self.vals)\n",
    "    \n",
    "    def push(self, val):\n",
    "        self.vals.append(val)\n",
    "        self.sift_up(len(self.vals) - 1)\n",
    "        return\n",
    "    \n",
    "    def pop(self):\n",
    "        if not self.vals:\n",
    "            return None\n",
    "        self.vals[0], self.vals[len(self.vals) - 1] = self.vals[len(self.vals) - 1], self.vals[0]\n",
    "        val = self.vals.pop()\n",
    "        if self.vals:\n",
    "            self.sift_down(0)\n",
    "        return val\n",
    "    \n",
    "    def sift_up(self, idx):\n",
    "        if idx == 0:\n",
    "            return\n",
    "        parent_idx = (idx - 1) // 2\n",
    "        if self.vals[idx] < self.vals[parent_idx]:\n",
    "            self.vals[idx], self.vals[parent_idx] = self.vals[parent_idx], self.vals[idx]\n",
    "            self.sift_up(parent_idx)\n",
    "        \n",
    "    def sift_down(self, idx):\n",
    "        min_idx = idx * 2 + 1\n",
    "        if min_idx >= len(self.vals):\n",
    "            return\n",
    "        right_idx = min_idx + 1\n",
    "        if right_idx < len(self.vals) and self.vals[right_idx] < self.vals[min_idx]:\n",
    "            min_idx = right_idx\n",
    "        if self.vals[idx] > self.vals[min_idx]:\n",
    "            self.vals[idx], self.vals[min_idx] = self.vals[min_idx], self.vals[idx]\n",
    "            self.sift_down(min_idx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 堆排序\n",
    "def heapsort2(nums):\n",
    "    heap = Heap()\n",
    "    for val in nums:\n",
    "        heap.push(val)\n",
    "    return [heap.pop() for i in range(len(heap))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapsort2([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 链表的实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 单向链表的节点\n",
    "class ListNode(object):\n",
    "    def __init__(self, item):\n",
    "        self.val = item\n",
    "        self.next = None\n",
    "        \n",
    "    def __lt__(self, other):\n",
    "        return self.val < other.val\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return self.val == other.val\n",
    "\n",
    "# 单向链表\n",
    "class SinglyLinkedList(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "    \n",
    "    def init_with_list(self, val_list):\n",
    "        if len(val_list) == 0:\n",
    "            return\n",
    "        self.head = ListNode(val_list[0])\n",
    "        x = self.head\n",
    "        for i in val_list[1:]:\n",
    "            x.next = ListNode(i)\n",
    "            x = x.next\n",
    "    \n",
    "    def get_node(self, index):\n",
    "        x = self.head\n",
    "        for i in range(index):\n",
    "            if not x:\n",
    "                return None\n",
    "            x = x.next\n",
    "        return x\n",
    "    \n",
    "    def get_length(self):\n",
    "        length = 0\n",
    "        x = self.head\n",
    "        while x:\n",
    "            x = x.next\n",
    "            length += 1\n",
    "        return length\n",
    "    \n",
    "    def append(self, item):\n",
    "        node = ListNode(item)\n",
    "        if self.head:\n",
    "            x = self.head\n",
    "            while x.next:\n",
    "                x = x.next\n",
    "            x.next = node\n",
    "        else:\n",
    "            self.head = node\n",
    "    \n",
    "    def insert_head(self, item):\n",
    "        x = ListNode(item)\n",
    "        x.next = self.head\n",
    "        self.head = x\n",
    "        \n",
    "    def to_list(self):\n",
    "        val_list = []\n",
    "        x = self.head\n",
    "        while x:\n",
    "            val_list.append(x.val)\n",
    "            x = x.next\n",
    "        return val_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 295. 数据流的中位数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。\n",
    "\n",
    "例如，\n",
    "\n",
    "[2,3,4] 的中位数是 3\n",
    "\n",
    "[2,3] 的中位数是 (2 + 3) / 2 = 2.5\n",
    "\n",
    "设计一个支持以下两种操作的数据结构：\n",
    "\n",
    "void addNum(int num) - 从数据流中添加一个整数到数据结构中。\n",
    "\n",
    "double findMedian() - 返回目前所有元素的中位数。\n",
    "\n",
    "示例：\n",
    "\n",
    "addNum(1)\n",
    "\n",
    "addNum(2)\n",
    "\n",
    "findMedian() -> 1.5\n",
    "\n",
    "addNum(3) \n",
    "\n",
    "findMedian() -> 2\n",
    "\n",
    "进阶:\n",
    "\n",
    "如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？\n",
    "\n",
    "如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 由于heapq未实现最大堆，所以将push(e)改为push(-e)、pop(e)改为-pop(e)来模拟最大堆的效果\n",
    "# 左边为最大堆，右边为最小堆，每次把一个元素推入并弹出最大堆，弹出的元素推入最小堆\n",
    "class MedianFinder:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.maxheap = []\n",
    "        self.minheap = []\n",
    "\n",
    "    def add_num(self, num):\n",
    "        heappush(self.minheap, -heappushpop(self.maxheap, -num))\n",
    "        if len(self.minheap) > len(self.maxheap):\n",
    "            heappush(self.maxheap, -heappop(self.minheap))        \n",
    "\n",
    "    def find_median(self):\n",
    "        if len(self.maxheap) == 0:\n",
    "            return None\n",
    "        if len(self.maxheap) == len(self.minheap):\n",
    "            return (self.minheap[0] - self.maxheap[0]) / 2\n",
    "        else:\n",
    "            return -self.maxheap[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "finder = MedianFinder()\n",
    "finder.add_num(1)\n",
    "finder.find_median()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.5"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "finder.add_num(2)\n",
    "finder.find_median()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "finder.add_num(3)\n",
    "finder.find_median()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.5"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "finder.add_num(-99)\n",
    "finder.find_median()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "finder = MedianFinder()\n",
    "finder.add_num(13)\n",
    "finder.add_num(7)\n",
    "finder.add_num(2)\n",
    "finder.add_num(10)\n",
    "finder.add_num(8)\n",
    "finder.add_num(4)\n",
    "finder.add_num(5)\n",
    "finder.find_median()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "进阶:\n",
    "\n",
    "如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MedianFinder2:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.freq = [0] * 101\n",
    "        self.length = 0\n",
    "\n",
    "    def add_num(self, num):\n",
    "        self.freq[num] += 1\n",
    "        self.length += 1\n",
    "    \n",
    "    def find_median(self):\n",
    "        count = 0\n",
    "        left = -1\n",
    "        for i in range(101):\n",
    "            count += self.freq[i]\n",
    "            if self.length % 2 == 1:\n",
    "                if count >= (self.length + 1) / 2: return i\n",
    "            else:\n",
    "                if left < 0 and count >= self.length / 2: left = i\n",
    "                if left >= 0 and count >= self.length / 2 + 1: return (left + i) / 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "finder = MedianFinder2()\n",
    "finder.add_num(1)\n",
    "finder.find_median()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.5"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "finder.add_num(2)\n",
    "finder.find_median()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "finder.add_num(3)\n",
    "finder.find_median()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.5"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "finder.add_num(0)\n",
    "finder.find_median()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "finder = MedianFinder()\n",
    "finder.add_num(13)\n",
    "finder.add_num(7)\n",
    "finder.add_num(2)\n",
    "finder.add_num(10)\n",
    "finder.add_num(8)\n",
    "finder.add_num(4)\n",
    "finder.add_num(5)\n",
    "finder.find_median()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 23. 合并K个排序链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。\n",
    "\n",
    "示例:\n",
    "\n",
    "输入:\n",
    "[\n",
    "  1->4->5,\n",
    "  1->3->4,\n",
    "  2->6\n",
    "]\n",
    "\n",
    "输出: 1->1->2->3->4->4->5->6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "from queue import PriorityQueue\n",
    "\n",
    "# 比较每个链表的首节点，获得最小值的节点。将选中的节点接在最终有序链表的后面。\n",
    "def merge_k_lists(lists):\n",
    "    queue = PriorityQueue()\n",
    "    dummy = ListNode(0)\n",
    "    x = dummy\n",
    "    for node in lists:\n",
    "        if node:\n",
    "            queue.put((node.val, node))\n",
    "    while not queue.empty():\n",
    "        val, node = queue.get()\n",
    "        x.next = node\n",
    "        x = x.next\n",
    "        node = node.next\n",
    "        if node:\n",
    "            queue.put((node.val, node))\n",
    "    return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 3, 4, 4, 5, 6]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list1 = SinglyLinkedList()\n",
    "list1.init_with_list([1,4,5])\n",
    "list2 = SinglyLinkedList()\n",
    "list2.init_with_list([1,3,4])\n",
    "list3 = SinglyLinkedList()\n",
    "list3.init_with_list([2,6])\n",
    "\n",
    "result = SinglyLinkedList()\n",
    "result.head = merge_k_lists([list1.head, list2.head, list3.head])\n",
    "result.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 使用heapq代替PriorityQueue\n",
    "def merge_k_lists2(lists):\n",
    "    queue = []\n",
    "    dummy = ListNode(0)\n",
    "    x = dummy\n",
    "    for node in lists:\n",
    "        if node:\n",
    "            heappush(queue, (node.val, node))\n",
    "    while queue:\n",
    "        val, node = heappop(queue)\n",
    "        x.next = node\n",
    "        x = x.next\n",
    "        node = node.next\n",
    "        if node:\n",
    "            heappush(queue, (node.val, node))\n",
    "    return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 3, 4, 4, 5, 6]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list1 = SinglyLinkedList()\n",
    "list1.init_with_list([1,4,5])\n",
    "list2 = SinglyLinkedList()\n",
    "list2.init_with_list([1,3,4])\n",
    "list3 = SinglyLinkedList()\n",
    "list3.init_with_list([2,6])\n",
    "\n",
    "result = SinglyLinkedList()\n",
    "result.head = merge_k_lists2([list1.head, list2.head, list3.head])\n",
    "result.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list1 = SinglyLinkedList()\n",
    "list1.init_with_list([])\n",
    "list2 = SinglyLinkedList()\n",
    "list2.init_with_list([])\n",
    "list3 = SinglyLinkedList()\n",
    "list3.init_with_list([])\n",
    "\n",
    "result = SinglyLinkedList()\n",
    "result.head = merge_k_lists2([list1.head, list2.head, list3.head])\n",
    "result.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list1 = SinglyLinkedList()\n",
    "list1.init_with_list([])\n",
    "list2 = SinglyLinkedList()\n",
    "list2.init_with_list([])\n",
    "list3 = SinglyLinkedList()\n",
    "list3.init_with_list([-1])\n",
    "\n",
    "result = SinglyLinkedList()\n",
    "result.head = merge_k_lists2([list1.head, list2.head, list3.head])\n",
    "result.to_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 373. 查找和最小的K对数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。\n",
    "\n",
    "定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。\n",
    "\n",
    "找到和最小的 k 对数字 (u1,v1), (u2,v2) ... (uk,vk)。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3\n",
    "输出: [1,2],[1,4],[1,6]\n",
    "\n",
    "解释: 返回序列中的前 3 对数：\n",
    "     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]\n",
    "     \n",
    "示例 2:\n",
    "\n",
    "输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2\n",
    "输出: [1,1],[1,1]\n",
    "\n",
    "解释: 返回序列中的前 2 对数：\n",
    "     [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]\n",
    "     \n",
    "示例 3:\n",
    "\n",
    "输入: nums1 = [1,2], nums2 = [3], k = 3 \n",
    "输出: [1,3],[2,3]\n",
    "\n",
    "解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 使用两个指针分别指向两个数组，每次从最小堆中取出一个最小对，然后分别使两个最小对的指针后移一位，将两组数对压入堆中\n",
    "def k_smallest_pairs(nums1, nums2, k):\n",
    "    if not nums1 or not nums2:\n",
    "        return []\n",
    "    heap = []\n",
    "    max_i, max_j = len(nums1), len(nums2)\n",
    "    output = []\n",
    "    visited = set()\n",
    "    heappush(heap, (nums1[0] + nums2[0], 0, 0))\n",
    "    while heap and k:\n",
    "        val, i, j = heappop(heap)\n",
    "        output.append([nums1[i], nums2[j]])\n",
    "        if i + 1 < max_i and (i + 1, j) not in visited:\n",
    "            heappush(heap, (nums1[i + 1] + nums2[j], i + 1, j))\n",
    "            visited.add((i + 1, j))\n",
    "        if j + 1 < max_j and (i, j + 1) not in visited:\n",
    "            heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))\n",
    "            visited.add((i, j + 1))\n",
    "        k -= 1\n",
    "    return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2], [1, 4], [1, 6]]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "k_smallest_pairs([1,7,11], [2,4,6], 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 1], [1, 1]]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "k_smallest_pairs([1,1,2], [1,2,3], 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 3], [2, 3]]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "k_smallest_pairs([1,2], [3], 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "k_smallest_pairs([], [], 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 451. 根据字符出现频率排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个字符串，请将字符串里的字符按照出现的频率降序排列。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入:\n",
    "\"tree\"\n",
    "\n",
    "输出:\n",
    "\"eert\"\n",
    "\n",
    "解释:\n",
    "'e'出现两次，'r'和't'都只出现一次。\n",
    "因此'e'必须出现在'r'和't'之前。此外，\"eetr\"也是一个有效的答案。\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入:\n",
    "\"cccaaa\"\n",
    "\n",
    "输出:\n",
    "\"cccaaa\"\n",
    "\n",
    "解释:\n",
    "'c'和'a'都出现三次。此外，\"aaaccc\"也是有效的答案。\n",
    "注意\"cacaca\"是不正确的，因为相同的字母必须放在一起。\n",
    "\n",
    "示例 3:\n",
    "\n",
    "输入:\n",
    "\"Aabb\"\n",
    "\n",
    "输出:\n",
    "\"bbAa\"\n",
    "\n",
    "解释:\n",
    "此外，\"bbaA\"也是一个有效的答案，但\"Aabb\"是不正确的。\n",
    "注意'A'和'a'被认为是两种不同的字符。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 快速排序\n",
    "def frequency_sort(s):\n",
    "    count = {}\n",
    "    for c in s:\n",
    "        if c in count:\n",
    "            count[c] += 1\n",
    "        else:\n",
    "            count[c] = 1\n",
    "    sorted_chars = sorted(count.items(), key=lambda x: x[1], reverse=True)\n",
    "    output = ''\n",
    "    for c, time in sorted_chars:\n",
    "        output += c * time\n",
    "    return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'eetr'"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "frequency_sort('tree')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'cccaaa'"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "frequency_sort('cccaaa')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'bbAa'"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "frequency_sort('Aabb')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a'"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "frequency_sort('a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "frequency_sort('')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 堆排序\n",
    "def frequency_sort2(s):\n",
    "    count = {}\n",
    "    for c in s:\n",
    "        if c in count:\n",
    "            count[c] += 1\n",
    "        else:\n",
    "            count[c] = 1\n",
    "    heap = []\n",
    "    for c, time in count.items():\n",
    "        heappush(heap, (-time, c))\n",
    "    output = ''\n",
    "    while heap:\n",
    "        time, c = heappop(heap)\n",
    "        output += c * (-time)\n",
    "    return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'eert'"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "frequency_sort2('tree')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'aaaccc'"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "frequency_sort2('cccaaa')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'bbAa'"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "frequency_sort2('Aabb')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a'"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "frequency_sort2('a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "frequency_sort2('')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 871. 最低加油次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。\n",
    "\n",
    "沿途有加油站，每个 station[i] 代表一个加油站，它位于出发位置东面 station[i][0] 英里处，并且有 station[i][1] 升汽油。\n",
    "\n",
    "假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。\n",
    "\n",
    "当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。\n",
    "\n",
    "为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。\n",
    "\n",
    "注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。\n",
    "\n",
    " \n",
    "\n",
    "示例 1：\n",
    "\n",
    "输入：target = 1, startFuel = 1, stations = []\n",
    "输出：0\n",
    "\n",
    "解释：我们可以在不加油的情况下到达目的地。\n",
    "\n",
    "示例 2：\n",
    "\n",
    "输入：target = 100, startFuel = 1, stations = [[10,100]]\n",
    "输出：-1\n",
    "\n",
    "解释：我们无法抵达目的地，甚至无法到达第一个加油站。\n",
    "\n",
    "示例 3：\n",
    "\n",
    "输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]\n",
    "输出：2\n",
    "\n",
    "解释：\n",
    "我们出发时有 10 升燃料。\n",
    "我们开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。\n",
    "然后，我们从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），\n",
    "并将汽油从 10 升加到 50 升。然后我们开车抵达目的地。\n",
    "我们沿途在1两个加油站停靠，所以返回 2 。\n",
    " \n",
    "\n",
    "提示：\n",
    "\n",
    "1 <= target, startFuel, stations[i][1] <= 10^9\n",
    "0 <= stations.length <= 500\n",
    "0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "def min_refuel_stops(target, startFuel, stations):\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3(py37)",
   "language": "python",
   "name": "py37"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
